package selected;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class J0822 {
    // 1.  除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 前缀和
        // 预处理一个前缀和数组和后缀和数组
        // f表示从（0- i）区间的所有数组的前缀积
        // g表示从（i - n-1）区间内所有数组的后缀积
        int[] f = new int[n];
        int[] g = new int[n];
        int[] ans = new int[n];

        f[0] = 1; g[n - 1] = 1;
        for(int i = 1; i < n; i++){
            f[i] = f[i - 1] * nums[i - 1];
        }
        for(int i = n - 2; i >= 0; i--){
            g[i] = g[i + 1] * nums[i + 1];
        }
        for(int i = 0; i < n; i++){
            ans[i] = f[i] * g[i];
        }
        return ans;
    }
    // 合并区间
    // 单调区间
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0){
            return new int[0][2];
        }
        // 按照左边界进行排序，这样左边界永远都是最小的
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] interval1, int[] interval2){
                return interval1[0] - interval2[0];
            }
        });

        List<int[]> ret = new ArrayList<>();
        ret.add(intervals[0]);
        for(int i = 1; i < intervals.length; i++){
            // 开始合并区间
            if(ret.get(ret.size() - 1)[1] >= intervals[i][0]){
                // 如果上一个数组的右边届大于当前数组的左边界，进行合并
                ret.get(ret.size() - 1)[1] = Math.max(ret.get(ret.size() - 1)[1], intervals[i][1]);
            } else {
                ret.add(intervals[i]);
            }
        }
        return ret.toArray(new int[ret.size()][2]);
    }
    //  缺失的第一个正数
    public int firstMissingPositive(int[] nums) {
        // 数组置换，不额外使用其他的数组
        int n = nums.length;
        for(int i = 0; i < n; i++){
            while(nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
                int corrent = nums[i] - 1;
                int tmp = nums[corrent];
                nums[corrent] = nums[i];
                nums[i] = tmp;
            }
        }
        for(int i = 0; i < n; i++){
            if(nums[i] !=  i + 1) return i + 1;
        }
        return n + 1;
    }
}
